package com.lhcai.lc.category.prefixsum;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 1658. 将 x 减到 0 的最小操作数
 *
 * @author liuhuaicai
 * @since 2024-10-20 15:26
 */
public class Lc1658 {
    public static void main(String[] args) {
        Lc1658 lc1658 = new Lc1658();
        System.out.println(lc1658.minOperations(new int[]{8828, 9581, 49, 9818, 9974, 9869, 9991, 10000, 10000, 10000, 9999, 9993, 9904, 8819, 1231, 6309}, 134635));
    }

    public int minOperations(int[] nums, int x) {
        // 数组的和
        int total = Arrays.stream(nums).sum();
        // x等于数组元素之和时，需要操作  nums.length 次
        if (total == x) {
            return nums.length;
        }
        // 转换为求数组中和为 k 的最大子数组
        int k = total - x;
        int max = Integer.MIN_VALUE;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (map.containsKey(sum - k)) {
                max = Math.max(max, i - map.get(sum - k));
            }
            map.put(sum, i);
        }
        return max == Integer.MIN_VALUE ? -1 : nums.length - max;
    }
}
